package com.study.algorithm.pathalgorithm.MIniTree.impl;

import com.study.algorithm.datastruct.graph.model.Edge;
import com.study.algorithm.datastruct.graph.model.Graph;
import com.study.algorithm.datastruct.graph.model.Vertex;
import com.study.algorithm.datastruct.tree.model.Tree;
import com.study.algorithm.pathalgorithm.MIniTree.MiniSpanningTree;

import java.util.*;
import java.util.stream.Collectors;

public abstract class MiniSpanningTreeImpl implements MiniSpanningTree {


    /**
     * 该算法对图的要求是应该能满足一个基本点
     * 给图中任意一个顶点A，那么A到其它顶点都至少有一个通路，才能生成最小生成树
     * 至于检测算法，没有写，如果你有兴趣可以自己完成
     *
     * @param graph
     * @return
     */
    @Override
    abstract public Tree getMiniSpanningTree(Graph graph);

    protected Tree generateTreeThroughEdges(Set<Vertex> vertices, Set<Edge> selectedEdge) {
        Set<Edge> edgesCopy = selectedEdge.stream().collect(Collectors.toSet());
        Vertex optimalRootVertex = analysisTheOptimalRootVertex(vertices, selectedEdge);
        return buildSubTree(optimalRootVertex, edgesCopy, 0);

    }

    private Tree buildSubTree(Vertex currRoootVertex, Set<Edge> edges, int distance) {
        Tree tree = new Tree();
        tree.setWeight(distance);
        tree.setData(currRoootVertex);
        Set<Edge> edgesContainVerties = findAllEdgesContainVertex(currRoootVertex, edges);
        if (edgesContainVerties == null || edgesContainVerties.size() == 0) {
            return tree;
        }

        edges.removeAll(edgesContainVerties);
        Iterator<Edge> it = edgesContainVerties.iterator();
        while (it.hasNext()) {
            Edge currEdge = it.next();
            Vertex currVertex1 = currEdge.getStartVetex();
            Vertex currVertex2 = currEdge.getEndVetex();
            int currDistance = currEdge.getDistance();
            Vertex nextVertex = currRoootVertex.equals(currVertex1) ? currVertex2 : currVertex1;
            Tree subTree = buildSubTree(nextVertex, edges, currDistance);
            tree.addChildNode(subTree);
        }
        return tree;
    }

    /**
     * 分析到大个点最低的节点作为根节点
     * 意义：最小生成树的实际意义是在（举例说明)
     * 图的每个顶点都代表一个需要粮食点，其中只有一个供粮点，
     * 具体选定谁作为这个供粮点，
     * 应该是各个需要粮食的点到该供粮点的代价应该最低的点
     *
     * @return
     */
    private Vertex analysisTheOptimalRootVertex(Set<Vertex> vertices, Set<Edge> edges) {
        int miniDistance = Integer.MAX_VALUE;
        Vertex optimalRootVertex = null;
        Iterator<Vertex> it = vertices.iterator();
        while (it.hasNext()) {

            Vertex rootVertex = it.next();
            Set<Edge> copyEdges = edges.stream().collect(Collectors.toSet());
            int distance = computeTatoalDistance(rootVertex, copyEdges);
            if (miniDistance <= distance) {
                continue;
            }
            miniDistance = distance;
            optimalRootVertex = rootVertex;
        }

        return optimalRootVertex;

    }


    private int computeTatoalDistance(Vertex startVertex, Set<Edge> edges) {
        Map<Vertex, Integer> recordDistances = new HashMap<>();
        int distance = 0;
        recordDistances.put(startVertex, distance);
        computSubVertexDistance(recordDistances, startVertex, edges);
        Iterator<Map.Entry<Vertex, Integer>> it = recordDistances.entrySet().iterator();

        while (it.hasNext()) {
            Map.Entry<Vertex, Integer> next = it.next();
            distance += next.getValue();
        }
        return distance;
    }


    private void computSubVertexDistance(Map<Vertex, Integer> recordDistances, Vertex currStartVertex, Set<Edge> edges) {
        Set<Edge> edgesContainVerties = findAllEdgesContainVertex(currStartVertex, edges);
        if (edgesContainVerties == null || edgesContainVerties.size() == 0) {
            return;
        }
        edges.removeAll(edgesContainVerties);
        Iterator<Edge> it = edgesContainVerties.iterator();
        while (it.hasNext()) {
            Edge currEdge = it.next();
            Vertex currVertex1 = currEdge.getStartVetex();
            Vertex currVertex2 = currEdge.getEndVetex();
            Vertex nextVertex = currStartVertex.equals(currVertex1) ? currVertex2 : currVertex1;
            int distance = computeStartVertexToVertexDistance(recordDistances, currStartVertex, currEdge.getDistance());
            recordDistances.put(nextVertex, distance);
            computSubVertexDistance(recordDistances, nextVertex, edges);
        }
    }

    private int computeStartVertexToVertexDistance(Map<Vertex, Integer> recordDistances, Vertex currStartVertex, int distance) {
        int preDistance = recordDistances.get(currStartVertex);
        return preDistance + distance;
    }

    private Set<Vertex> filterNextStartVertexSet(Vertex vertex, Set<Edge> edges) {
        return edges.stream().map(e -> {
            Vertex vertex1 = e.getStartVetex();
            Vertex vertex2 = e.getEndVetex();
            Vertex returnVertex = vertex.equals(vertex1) ? vertex2 : vertex1;
            return returnVertex;
        }).collect(Collectors.toSet());
    }

    protected Set<Edge> findAllEdgesContainVertex(Vertex vertex, Set<Edge> edges) {
        if (edges == null || edges.size() == 0) {
            return null;
        }
        return edges.stream().filter(e -> {
            Vertex vertex1 = e.getStartVetex();
            Vertex vertex2 = e.getEndVetex();
            return vertex.equals(vertex1) || vertex.equals(vertex2);
        }).collect(Collectors.toSet());
    }

    protected Set<Edge> sortEdgesDesc(Set<Edge> edges) {
        Set<Edge> resultSet = edges.stream()
                .sorted(
                        (e1, e2) -> {
                            Integer distance1 = e1.getDistance();
                            Integer distance2 = e2.getDistance();
                            distance1 = distance1 == null || distance1 == -1
                                    ? Integer.MAX_VALUE : distance1;
                            distance2 = distance2 == null || distance2 == -1
                                    ? Integer.MAX_VALUE : distance2;
                            return distance1.compareTo(distance2);
                        }
                )
                .collect(Collectors.toCollection(LinkedHashSet::new));

        return resultSet;
    }

    protected boolean isExistPathFromVertexToVertex(Set<Edge> selectedEdge, Vertex vertex, Vertex vertex1) {

        boolean isExist = false;
        Set<Edge> edgesContainVerties = findAllEdgesContainVertex(vertex, selectedEdge);
        if (edgesContainVerties == null || edgesContainVerties.size() == 0) {
            return isExist;
        }
        selectedEdge.removeAll(edgesContainVerties);
        Iterator<Edge> it = edgesContainVerties.iterator();
        while (it.hasNext()) {
            Edge currEdge = it.next();
            Vertex currVertex1 = currEdge.getStartVetex();
            Vertex currVertex2 = currEdge.getEndVetex();
            Vertex nextVertex = vertex.equals(currVertex1) ? currVertex2 : currVertex1;
            if (nextVertex.equals(vertex1)) {
                isExist = true;
                break;
            }
            if (isExistPathFromVertexToVertex(selectedEdge, nextVertex, vertex1)) {
                isExist = true;
                break;
            }
        }
        return isExist;
    }

}
